package main

/*
	给你一个链表，删除链表的倒数第n个节点，并且返回链表的头节点
*/
func removeNthFromEnd(head *ListNode, n int) *ListNode{
	//可以考虑设置一个指向头节点的哑节点，将pSecond指向哑节点，这样就不需要单独考虑删除头节点的情况
	//双指针，快指针比慢指针先走n-1步
	dummy := &ListNode{0,head}
	pSecond := dummy
	pFirst := head
	for i:=0;i<n-1;i++{
		pFirst = pFirst.Next
	}
	for{
		if pFirst.Next == nil{
			break
		}
		pFirst = pFirst.Next
		pSecond = pSecond.Next
	}
	pSecond.Next = pSecond.Next.Next

	return dummy.Next
	//pFirst := head
	//pSecond := head
	//for i := 0; i < n; i++ {
	//	//快指针先走n步
	//	pFirst = pFirst.Next
	//}
	//if pFirst == nil{
	//	//删除头节点
	//	head = head.Next
	//}else{
	//	for {
	//		if pFirst.Next == nil {
	//			//当pFirst指向最后一个节点时，pSecond指向目标节点的前一个节点
	//			break
	//		}
	//		pFirst = pFirst.Next
	//		pSecond = pSecond.Next
	//	}
	//	//删除pSecond.next
	//	pTemp := pSecond.Next.Next
	//	pSecond.Next = pTemp
	//}
	//return head
}
